package com.leet;

import java.util.List;

/**
 * Hello world!
 */
public class App {


    boolean ans = false;
    void backTracking(char[][] board, String word,int k,int i,int j,boolean[][] visited){
        if(k==word.length()){
            ans = true;
            return;
        }
        if(i<0||i>=board.length||j<0||j>=board[0].length||word.charAt(k)!=board[i][j]||visited[i][j]){
            return;
        }
        visited[i][j]=true;
        backTracking(board,word,k+1,i-1,j,visited);
        backTracking(board,word,k+1,i+1,j,visited);
        backTracking(board,word,k+1,i,j-1,visited);
        backTracking(board,word,k+1,i,j+1,visited);
        visited[i][j]=false;

    }

    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        for(int i = 0;i < board.length;i++){
            for(int j = 0;j <board[0].length;j++){
                backTracking(board,word,0,i,j,visited);
            }
        }

        return ans;
    }

}
